class Node {
    constructor (element) {
      this.element = element
      this.next = null
    }
}
// 双向链表的节点类（继承单向链表的节点类）
class DoublyNode extends Node {
    constructor(element) {
      super(element);
      this.prev = null;
    }
}



class LinkedList {
    constructor (equalsFn = defaultEquals) {
      this.count = 0
      this.head = null
      this.equalsFn = equalsFn
    }

    // 向链表尾部添加元素
    push (element) {
        let current = null
        const node = new Node(element)
        if (this.head === null) {
          this.head = node
        } else {
          current = this.head
          while (current.next !== null) {
            current = current.next
          }
          current.next = node
        }
        this.count++
    }

    //迭代链表直到目标位置
    getElementAt (index) {
        if (index >= 0 && index <= this.count) {
          let current = this.head
          for (let i = 0; i < index && current !== null; i++) {
            current = current.next
          }
          return current
        }
        return undefined
    }

    // 从链表中移除指定位置元素
    removeAt (index) {
        if (index >= 0 && index < this.count) {
          let current = this.head
          if (index === 0) {
            this.head = current.next
          } else {
            const previous = this.getElementAt(index - 1)
            current = previous.next
            previous.next = current.next
          }
          this.count--
          return current.element
        }
        return undefined
    }

    // 在任意位置插入元素
    insert (element, index) {
        if (index >= 0 && index <= this.count) {
          const node = new Node(element)
          if (index === 0) {
            const current = this.head
            node.next = current
            this.head = node
          } else {
            const previous = this.getElementAt(index - 1)
            const current = previous.next
            node.next = current
            previous.next = node
          }
          this.count++
          return true
        }
        return false
    }

    // 返回一个元素的位置
    indexOf (element) {
        let current = this.head
        for (let index = 0; index < this.count && current !== null; index++) {
          if (this.equalsFn(element, current.element)) {
            return index
          }
          current = current.next
        }
        return -1
    }

    // 从链表中移除元素
    remove (element) {
        let index = this.indexOf(element)
        return this.removeAt(index)
    }


    // 其他方法
    size () {
        return this.count
    }
    isEmpty() {
        return this.size() === 0
    }
    getHead () {
        return this.head === null ? undefined : this.head.element
    }
    toString () {
        if (this.isEmpty()) {
          return ''
        }
        let str = this.head.element
        let current = this.head

        while(current.next !== null) {
          current = current.next
          str = `${str},${current.element}`
        }
        return str
    }

}



// 双向链表类继承单向链表类
class DoublyLinkedList extends LinkedList {
    constructor() {
      super();
      this.tail = null;
    }

    // append(element) 往双向链表尾部追加一个新的元素
    // 重写 append()
    append(element) {
        // 1、创建双向链表节点
        const newNode = new DoublyNode(element);
        // 2、追加元素
        if (this.head === null) {
            this.head = newNode;
            this.tail = newNode;
            } else {
            // ！！跟单向链表不同，不用通过循环找到最后一个节点
            // 巧妙之处
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        }
        this.length++;
    }

    // 重写 insert()
    insert(position, element) {
        // 1、position 越界判断
        if (position < 0 || position > this.length) return false;
        // 2、创建新的双向链表节点
        const newNode = new DoublyNode(element);
        // 3、判断多种插入情况
        if (position === 0) { // 在第 0 个位置插入
            if (this.head === null) {
                this.head = newNode;
                this.tail = newNode;
            } else {
                //== 巧妙之处：相处腾出 this.head 空间，留个 newNode 来赋值 ==//
                newNode.next = this.head;
                this.head.perv = newNode;
                this.head = newNode;
            }

        } else if (position === this.length) { // 在最后一个位置插入
            this.tail.next = newNode;
            newNode.prev = this.tail;
            this.tail = newNode;
        } else { // 在 0 ~ this.length 位置中间插入
            let targetIndex = 0;
            let currentNode = this.head;
            let previousNode = null;

            // 找到要插入位置的节点
            while (targetIndex++ < position) {
                previousNode = currentNode;
                currentNode = currentNode.next;
            }
            // 交换节点信息
            previousNode.next = newNode;
            newNode.prev = previousNode;
            newNode.next = currentNode;
            currentNode.prev = newNode;
        }
        this.length++;
        return true;
    }


    // removeAt() 删除指定位置的节点
    // 重写 removeAt()
    removeAt(position) {
        // 1、position 越界判断
        if (position < 0 || position > this.length - 1) return null;
        // 2、根据不同情况删除元素
        let currentNode = this.head;
        if (position === 0) { // 删除第一个节点的情况

            if (this.length === 1) { // 链表内只有一个节点的情况
                this.head = null;
                this.tail = null;
            } else { // 链表内有多个节点的情况
                this.head = this.head.next;
                this.head.prev = null;
            }

        } else if (position === this.length - 1) { // 删除最后一个节点的情况

            currentNode = this.tail;
            this.tail.prev.next = null;
            this.tail = this.tail.prev;

        } else { // 删除 0 ~ this.length - 1 里面节点的情况

            let targetIndex = 0;
            let previousNode = null;
            while (targetIndex++ < position) {
                previousNode = currentNode;
                currentNode = currentNode.next;
            }
            previousNode.next = currentNode.next;
            currentNode.next.perv = previousNode;
        }
        this.length--;
        return currentNode.data;
    }


    // update(position, data) 修改指定位置的节点
    // 重写 update()
    update(position, data) {
        // 1、删除 position 位置的节点
        const result = this.removeAt(position);

        // 2、在 position 位置插入元素
        this.insert(position, data);
        return result;
    }



    // forwardToString() 链表数据从前往后以字符串形式返回
    forwardToString() {
        let currentNode = this.head;
        let result = '';
        // 遍历所有的节点，拼接为字符串，直到节点为 null
        while (currentNode) {
            result += currentNode.data + '--';
            currentNode = currentNode.next;
        }
        return result;
    }


    // backwardString() 链表数据从后往前以字符串形式返回
    backwardString() {
        let currentNode = this.tail;
        let result = '';
        // 遍历所有的节点，拼接为字符串，直到节点为 null
        while (currentNode) {
            result += currentNode.data + '--';
            currentNode = currentNode.prev;
        }
        return result;
    }





    // getData() 继承单向链表
    getData(position) {
        return super.getData(position);
    }

    // indexOf() 继承单向链表
    indexOf(data) {
        return super.indexOf(data);
    }

    // remove(data) 删除指定 data 所在的节点（继承单向链表）
    remove(data) {
        return super.remove(data);
    }

    // isEmpty() 判断链表是否为空
    isEmpty() {
        return super.isEmpty();
    }

    // size() 获取链表的长度
    size() {
        return super.size();
    }



}



const doublyLinkedList = new DoublyLinkedList();

// append() 测试
doublyLinkedList.append("ZZ");
doublyLinkedList.append("XX");
doublyLinkedList.append("CC");
console.log(doublyLinkedList);

// insert() 测试
doublyLinkedList.insert(0, "00");
doublyLinkedList.insert(2, "22");
console.log(doublyLinkedList);

// getData() 测试
console.log(doublyLinkedList.getData(1)); //--> ZZ

// indexOf() 测试
console.log(doublyLinkedList.indexOf("XX")); //--> 3
console.log(doublyLinkedList);


// removeAt() 测试
doublyLinkedList.removeAt(0);
doublyLinkedList.removeAt(1);
console.log(doublyLinkedList);

// update() 测试
doublyLinkedList.update(0, "111111");
console.log(doublyLinkedList);

// remove() 测试
console.log(doublyLinkedList.remove("111111"));
console.log(doublyLinkedList.remove("22222"));
console.log(doublyLinkedList);

// forwardToString() 测试
console.log(doublyLinkedList.forwardToString());

// backwardString() 测试
console.log(doublyLinkedList.backwardString());